package com.yulan.Tree;

import org.junit.Test;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 297. 二叉树的序列化与反序列化 bfs
 */
public class LeetCode_297_bfs {
    private class Codec{

        public String serialize(TreeNode root) {
            StringBuilder ans = new StringBuilder();
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while(!queue.isEmpty()){
                TreeNode curNode = queue.poll();
                if(curNode == null){
                    ans.append("null");
                }else{
                    ans.append(curNode.val);
                    queue.offer(curNode.left);
                    queue.offer(curNode.right);
                }
                ans.append(",");
            }
            return ans.toString();
        }

        public TreeNode deserialize(String data) {
            String[] datas = data.split(",");
            Queue<TreeNode> queue = new LinkedList<>();
            if(datas[0].equals("null")) return null;
            TreeNode root = new TreeNode(Integer.valueOf(datas[0]));
            queue.offer(root);
            int index = 1;
            while(!queue.isEmpty()){
                TreeNode curNode = queue.poll();
                if(curNode == null){
                    continue;
                }

                curNode.left = datas[index] .equals("null")  ? null : new TreeNode(Integer.valueOf(datas[index]));
                curNode.right = datas[index+1] .equals("null" ) ? null : new TreeNode(Integer.valueOf(datas[index+1]));
                index += 2;
                queue.offer(curNode.left);
                queue.offer(curNode.right);
            }
            return root;
        }
    }

    public void outTree(TreeNode root){
        if(root!=null){
            System.out.print(root.val+" ");
            outTree(root.left);
            outTree(root.right);
        }
    }

    @Test
    public void test(){
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        node1.left = node2;
        node1.right = node3;
        node3.left = node4;
        node3.right = node5;

        Codec codec = new Codec();

        String str = codec.serialize(null);
        System.out.println(str);

        TreeNode root = codec.deserialize(str);
        outTree(root);
    }
}
